// #include <iostream>

// template<typename InputIterator,
//          typename T>
// InputIterator find(InputIterator first, InputIterator last, const T& val)
// {
//     while (first != last)
//     {
//         ++first;
//     }
//     return first;
// }

// template<typename T>
// class ListItem
// {
//     private:
//         T _data;
//         ListItem* _next;
    
//     public:
//         T value() const { return _data; }
//         ListItem* next() const { return _next;}

//         ListItem() : _data(0), _next(nullptr) {}
//         ListItem(T data, ListItem* next) : _data(data), _next(next) {}
//         ListItem(const T& data) : _data(data), _next(nullptr) {}

//         ~ListItem()
//         {
//             if(_next!= nullptr) delete _next;    
//         }
// };

// template<typename T>
// class List
// {
//     private:
//         ListItem<T>* _front;
//         ListItem<T>* _end;
//         std::size_t _size;

//     public:
//         List()
//         {
//             _front = new ListItem<T>();
//             _end = _front;
//             _size = 0;
//         }

//         ~List()
//         {
            
//         }

// };

#include <iostream>
#include <iterator>
#include <cmath>
#include <vector>
#include <deque>

#include "hamster_demangle.h"

template<typename T>
class List
{
    public:
        using size_type = std::size_t;
        using value_type = T;
        using pointer_type = T*;
        using reference_type = T&;
        using const_pointer_type = const T*;
        using const_reference_type = const T&;
        // using iterator_category = std::bidirectional_iterator_tag;

        // List Node
        struct _Node;
        using _Nodeptr = _Node*;
        struct _Node
        {
            _Nodeptr _Next;
            _Nodeptr _Prev;
            value_type _value;
        };

        // List Allocator
        struct _Allocator
        {
            using _Nodeptr_Ref = _Nodeptr&;
            using _VRef = value_type&;

            static _Nodeptr_Ref _Next(_Nodeptr _P)
            {
                return _P->_Next;
            }

            static _Nodeptr_Ref _Prev(_Nodeptr _P)
            {
                return _P->_Prev;
            }

            static _VRef _Value(_Nodeptr _P)
            {
                return _P->_value;
            }
        };
        
    public:
        explicit List() : _Head(_Buynode()), _Size(0) {}

    protected:
        _Nodeptr _Buynode(
            _Nodeptr _Narg = nullptr,
            _Nodeptr _Parg = nullptr
        )
        {
            _Nodeptr _S = new _Node;
            _Allocator::_Next(_S) = _Narg != nullptr ? _Narg : _S;
            _Allocator::_Prev(_S) = _Parg != nullptr ? _Parg : _S;
            return _S;
        }

    public:
        void push_back(const value_type& _value)
        {
            _Nodeptr _S = new _Node;
            // bidirectional list
            _S->_value = _value;
            _S->_Prev = _Head->_Prev;
            _S->_Next = _Head;
            _Head->_Prev = _S;
            _S->_Prev->_Next = _S;
            ++_Size;
        }

        void push_back2(const value_type& _value)
        {
            _Nodeptr _S = _Buynode(
                _Head, _Allocator::_Prev(_Head)
            );
            _Allocator::_Value(_S) = _value;
            _Allocator::_Next(_Allocator::_Prev(_S)) = _S;
            _Allocator::_Prev(_Allocator::_Next(_S)) = _S;
            ++_Size;
        }

        // ~List() 
        // {
        //     _Nodeptr current = _Head->_Next;
        //     while (current != _Head) {
        //         _Nodeptr temp = current;
        //         current = current->_Next;
        //         delete temp;
        //     }
        //     delete _Head;
        // }

        ~List()
        {
            _Nodeptr current = _Allocator::_Next(_Head);
            while(current != _Head)
            {
                _Nodeptr temp = current;
                current = _Allocator::_Next(current);
                delete temp;
            }
            delete _Head;
        }

        template<typename U>
        friend std::ostream& print(std::ostream& os, const List<U>& _list);

    // Iterator for list
    public:
        class Iterator : public std::iterator<std::bidirectional_iterator_tag, T>
        {
            private:
                _Nodeptr _Ptr;

            public:
                Iterator() : _Ptr(nullptr) {}
                Iterator(_Nodeptr _P) : _Ptr(_P) {}
                using iterator_category = std::bidirectional_iterator_tag;
            
            public:
                bool operator==(const Iterator& _it)
                {
                    return _Ptr == _it._Ptr;
                }

                bool operator!=(const Iterator& _it)
                {
                    return _Ptr != _it._Ptr;
                }

                reference_type operator*()
                {
                    return _Allocator::_Value(_Ptr);
                }

                Iterator& operator++()
                {
                    _Ptr = _Allocator::_Next(_Ptr);
                    return *this;
                }

                Iterator operator++(int)
                {
                    Iterator _Tmp(_Ptr);
                    ++(*this);
                    return _Tmp;
                }
                
                // pre-decrement
                Iterator& operator--()
                {
                    _Ptr = _Allocator::_Prev(_Ptr);
                    return *this;
                }

                // post-decrement
                Iterator operator--(int)
                {
                    Iterator _Tmp(_Ptr);
                    --(*this);
                    return _Tmp;
                }
        };
    
    public:
        Iterator begin() const
        {
            return Iterator(_Allocator::_Next(_Head));
        }

        Iterator end() const
        {
            return Iterator(_Head);
        }

    private:
        _Nodeptr _Head;
        size_type _Size;
};

// template<typename T>
// struct my_iterator_traits
// {
//     using value_type = std::remove_cv_t<std::remove_reference_t<T>>;
//     // using pointer = value_type*;
//     using reference = value_type&;
// };

// // partial specialization for pointer type
// template<typename T>
// struct my_iterator_traits<T*>
// {
//     using value_type = std::remove_cv_t<std::remove_pointer_t<T>>;
//     using pointer = value_type*;
//     using reference = value_type&;
//     if(std::is_pointer_v<T>)
//     {
//         using value_type = std::remove_cv_t<std::remove_pointer_t<T>>;
//         using pointer = value_type*;
//         using reference = value_type&;
//     }
// };

// using type_traits head file
// template<typename T>
// struct my_iterator_traits
// {
//     if constexpr (std::is_pointer_v<T>)
//     {
//         using value_type = std::remove_cv_t<std::remove_pointer_t<T>>;
//         using pointer = value_type*;
//         using reference = value_type&;
//     }
//     else if constexpr (std::is_reference_v<T>)
//     {
//         using value_type = std::remove_cv_t<std::remove_reference_t<T>>;
//         using pointer = value_type*;
//         using reference = value_type&;
//     }
// };
// Wrong -> Because `if constexpr` is not supported in class type, only in function type.
// Solved -> Using std::conditional_t<>
template<typename T>
struct my_iterator_traits
{
    using value_type = std::conditional_t<
        std::is_pointer_v<T>,
        std::remove_cv_t<std::remove_pointer_t<T>>,
        std::remove_cv_t<std::remove_reference_t<T>>>;
    using pointer = value_type*;
    using lvalue_reference = value_type&;
    using rvalue_reference = value_type&&;

    using const_pointer = const value_type*;
    using const_lvalue_reference = const value_type&;
};

// No implementation of iterator for list
// template<typename T>
// std::ostream& print(std::ostream& os, const List<T>& _list)
// {
//     using _Nodeptr = typename List<T>::_Nodeptr;   
//     _Nodeptr current = List<T>::_Allocator::_Next(_list._Head);
//     while (current != _list._Head)  
//     {
//         auto value = List<T>::_Allocator::_Value(current);
//         // os << value << " --> ";
//         // current = List<T>::_Allocator::_Next(current);
//         _Nodeptr next = List<T>::_Allocator::_Next(current);
//         if(next == _list._Head)
//             os << value << std::endl;
//         else
//             os << value << " --> ";
//         current = next;
//     }
//     return os;
// }

// After implementation the iterator for list
template<typename T>
std::ostream& print(std::ostream& os, const List<T>& _list)
{
    auto it = _list.begin();
    while(it != _list.end())
    {
        if(*it != *(--_list.end()))
            os << *it << "-->";
        else
            os << *it << std::endl;
        ++it;
    }
    return os;
}

// template<typename InputIterator,
//          typename T>
// InputIterator my_find(InputIterator first, InputIterator last, const T& val)
// {
//     std::cout << __PRETTY_FUNCTION__ << std::endl;
//     while (first != last && *first != val)
//         ++first;
//     return first;
// }

template <class InputIterator, class T>
InputIterator my_find(InputIterator first, InputIterator last, const T& val) {
    std::cout << __PRETTY_FUNCTION__ << std::endl;
    while (first != last) {
        if (*first == val) return first; 
        ++first;                         
    }
    return last;
}

// template<class InputIterator>
// InputIterator my_find2(InputIterator first, InputIterator last, const float& val)
// {
//     std::cout << __PRETTY_FUNCTION__ << std::endl;
//     while (first != last) {
//         if (std::fabs(*first - val) < 0.0001)  return first; 
//         ++first;                          
//     }
//     return last;
// }


int main()
{
    List<int> mylist;
    mylist.push_back2(1);
    mylist.push_back2(2);
    print(std::cout, mylist);

    List<float> mylist2;
    mylist2.push_back2(1.1);
    mylist2.push_back2(2.2);
    auto it = mylist2.begin();
    while(it != mylist2.end())
    {
        if(*it != *(--mylist2.end()))
            std::cout << *it << "-->";
        else
            std::cout << *it << std::endl;
        ++it;
    }

    auto temp_find = my_find(mylist.begin(), mylist.end(), 1);
    std::cout << "temp_find: " << *temp_find << std::endl;

    auto temp_find2 = my_find(mylist2.begin(), mylist2.end(), 1.1f);
    std::cout << "temp_find2: " << *temp_find2 << std::endl;

    auto temp_find3 = std::find(mylist.begin(), mylist.end(), 1);
    std::cout << "temp_find3: " << *temp_find3 << std::endl;
    
    // test type traits
    std::cout << "value_type: " 
    << hamster::demangle<my_iterator_traits<int>::value_type>() << std::endl;
    std::cout << "pointer: " 
    << hamster::demangle<my_iterator_traits<int*>::pointer>() << std::endl;
    // Wrong -> the output is "pointer: int*" -> because the template type is deduced as "int*"
    // After implementation for the partial specialization for pointer type, the output is "pointer: T*"
    std::cout << "lvalue_reference: " 
    << hamster::demangle<my_iterator_traits<int&>::lvalue_reference>() << std::endl;
    
    // Assume we don't know a vector<double> element type
    std::vector<double> vec;

    // Using my_iterator_traits to deduce the element type of the vector
    std::cout << "vector element type: "
    << hamster::demangle<my_iterator_traits<decltype(*vec.begin())>::value_type>() << std::endl;
    
    // Prove that different stl use different iterator
    std::cout << "std::vector<double>::iterator type is : "
    << hamster::demangle<my_iterator_traits<decltype(vec.begin())>::value_type>() << std::endl;

    std::deque<double> deq;
    std::cout << "std::deque<double>::iterator type is : "
    << hamster::demangle<my_iterator_traits<decltype(deq.begin())>::value_type>() << std::endl;
    
    return 0;
}